package leetcode.D2000.T1462;

import java.util.*;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-17 13:31:19 星期四
 */

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        Set<Integer>[] fromGraph = buildGraph(numCourses, prerequisites, true);
        Set<Integer>[] toGraph = buildGraph(numCourses, prerequisites, false);
        Set<Integer> cand = new HashSet<>();
        for (int i=0; i<numCourses; ++i) {
            if (fromGraph[i].isEmpty())
                cand.add(i);
        }
        Deque<Integer> stack = new LinkedList<>();
        for (Integer v : cand) {
            stack.push(v);
        }
        cand.clear();
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i=0; i<numCourses; ++i)
            map.put(i, new HashSet<>());
        while(!stack.isEmpty()) {
            int top = stack.pop();
            for (int v : toGraph[top]) {
                fromGraph[v].remove(top);
                map.get(v).add(top);
                map.get(v).addAll(map.get(top));
                if (fromGraph[v].isEmpty())
                    cand.add(v);
            }
            for (int v : cand)
                stack.push(v);
            cand.clear();
        }

        List<Boolean> results = new ArrayList<>();
        for(int i=0; i<queries.length; ++i)
            results.add(map.get(queries[i][1]).contains(queries[i][0]));
        return results;
    }

    private Set<Integer>[] buildGraph(int numCourses, int[][] prerequisites, boolean isFrom) {
        Set<Integer>[] graph = new Set[numCourses];
        for (int i=0; i<numCourses; ++i)
            graph[i] = new HashSet<>();
        for(int i=0; i<prerequisites.length; ++i) {
            int from = prerequisites[i][0], to = prerequisites[i][1];
            if (isFrom)
                graph[to].add(from);
            else
                graph[from].add(to);
        }
        return graph;
    }
}